package problem134;

class Solution {
    public static int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        for(int i = 0; i<n; i++) {
            int index = i, step = 0;
            if(gas[i] - cost[i] >= 0) {
                int rest = 0;
                for(step = 0; step<n; step++) {
                    index = (i + step) % n;
                    rest = rest + gas[index] - cost[index];
                    if(rest < 0) {
                        break;
                    }
                }
                if(rest >= 0) return i;
            }
            i += step;
        }
        return -1;
    }
}